package tree.递归;

import po.TreeNode;

import java.time.LocalDate;
import java.util.*;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N路径总和II113.java
 * @Description TODO https://leetcode-cn.com/problems/path-sum-ii/
 * @createTime 2021年04月06日 12:54:00
 */
public class N路径总和II113 {
    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> deque = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return result;
    }

    /**
     * todo 在递归之前做出选择，在递归之后撤销刚才的选择
     * <p>
     * if 满足结束条件:
     *         result.add(路径)
     *         return
     * for 选择 in 选择列表:
     *   #剪枝
     *     if 不满足条件：
     *       跳过当前选择
     *   # 做选择
     *     将该选择从选择列表移除
     *     路径.add(选择)
     *     backtrack(路径, 选择列表)
     *   # 撤销选择
     *     路径.remove(选择)
     *     将该选择再加入选择列表
     */
    private void dfs(TreeNode root, int targetSum) {
        //判断选择合适不合适
        if (root == null) {
            return;
        }
        //满足结束条件
        /**
         * #做选择，
         *   路径add(选择)
         */
        deque.offerLast(root.val);
        targetSum -= root.val;
        if (root.left == null && root.right == null && targetSum == 0) {
            result.add(new LinkedList<Integer>(deque));
        }



        //进入下一层决策树
        dfs(root.left, targetSum);
        dfs(root.right, targetSum);

        /**
         * #取消选择,
         *  路径.remove(选择)
         */
        deque.pollLast();
    }
}
